﻿//1793. 好子数组的最大分数
//给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
//一个子数组(i, j) 的 分数 定义为 min(nums[i], nums[i + 1], ..., nums[j]) * (j - i + 1) 。
//一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
//请你返回 好 子数组的最大可能 分数 。


class Solution {
public:
    int maximumScore(vector<int>& nums, int k)
    {
        nums.push_back(0);
        nums.insert(nums.begin(), 0);
        int n = nums.size();
        int ans = 0;
        stack<int> sta;
        for (int i = 0; i < n; i++)
        {
            //单调递增
            while (!sta.empty() && nums[i] < nums[sta.top()])
            {
                int h = nums[sta.top()];
                sta.pop();
                if (k + 1 <= i - 1 && sta.top() + 1 <= k + 1)
                    ans = max(ans, (i - sta.top() - 1) * h);
            }
            sta.push(i);
        }
        return ans;

    }
}; 